package 树.堆排序;

/**
 * Created by yang on 2016/8/28.
 */
public class HeapSort {

    public int[] heapSortOfMaxHeap(int[] data) {

        data = createMaxHeap(data);
        return adjustMaxHeap(data);
    }

    /**122,87,78,45,17,65,53,9,32,
     * create a maxheap tree.
     * @param data
     * @return
     */
    public int[] createMaxHeap (int[] data) {

        int length = data.length;
        int index = length/2 - 1;

        for (int i = index; i >= 0; i--) {
            if (2 * i+2 < length) {
                // 满二叉树
                // 先比较两个孩子节点
                if (data[2*i+1] > data[2*i+2]) {
                    if (data[2*i+1] > data[i]) {
                        swap(data, 2*i+1, i);
                    }
                }else {
                    if (data[2*i+2] > data[i]) {
                        swap(data , 2*i+2 , i);
                    }
                }
            }else {
                // 最后的非叶子节点没有右孩子
                // 如果左孩子大于根节点，交换
                if (data[2*i+1] > data[i]) {
                    swap(data, 2*i+1 , i);
                }
            }
        }
        return data;
    }

    public void swap(int[] data , int indexOf1 , int indexOf2) {
        data[indexOf1] = data[indexOf1] ^ data[indexOf2];
        data[indexOf2] = data[indexOf1] ^ data[indexOf2];
        data[indexOf1] = data[indexOf1] ^ data[indexOf2];
    }

    public int[] adjustMaxHeap(int[] data) {

        int length = data.length;
        int indexOf1 = length - 1;// 8

        //第一个元素和最后一个未交换的元素交换
        // 直到i=0，最后一个元素无需比较，退出
        for (int i = indexOf1; i > 0; i--) {
            swap(data, 0, i);
            // 保存交换的值，判断截止调整的条件
            int swap = data[i];
            int indexOf2 = (i-1)/2;
            // 自上而下调整堆，直到index-1
            for (int j = 0; j <= indexOf2; j++) {
                // 判断是否到indexOf2
                if (j == indexOf2) {
                    //判断最后的节点情况
                    // 如果交换的时右节点，才会存在调整
                    // 可能最后一个非叶子节点没有右子树，即2*j+2 < length
                    if (2*j+2 < length && data[2*j+2] == swap) {
                        // 右孩子是被交换的节点，只比较左孩子
                        if (data[2*j+1] > data[j]) {
                            swap(data,2*j+1,j);
                        }
                    }
                }else {
                    // 还没有到被交换的子树
                    if (data[2*j+2] > data[2*j+1]) {
                        if (data[2*j+2] > data[j]) {
                            swap(data,2*j+2,j);
                        }
                    }else {
                        if (data[2*j+1] > data[j]) {
                            swap(data,2*j+1,j);
                        }
                    }
                }
            }

        }
        return data;
    }

    /**
     * create a minHeap tree
     * 对于第i个节点，其左孩子是i*2+1,右孩子是i*2+2
     * 1. 找到叶子节点，无需排序
     * 2. 从叶子节点的上一层节点开始排序即n/2 - i(i=1,2,3...)
     * 3. i每次递增前，从孩子节点中找到最小的，和父节点交换
     * {9,12,17,30,50,20,60,65,4,49}
     * @param data Ready to sort
     *
     */
    public int[] createMinHeap (int[] data) {

        int length = data.length;
        int index = length/2 - 1;

        // 整个操作无需转换为二叉树，因为每个节点和孩子节点有如下对应关系
        // 关系：对于第i个节点，其左孩子是i*2+1,右孩子是i*2+2
        //
        // 每次只需要比较父亲节点、左孩子、右孩子
        // 取出左孩子和右孩子中最小的节点和父节点比较
        // 最小的孩子还是小于父节点，才会交换
        // 叶子节点没有孩子，所以从叶子节点的上一个节点开始查找
        // 倒数第一个非叶子节点满足条件data[data.length/2 - 1]
        for (int i = index; i >= 0; i--) {

            //假如是满二叉树，先比较最后一个节点
            // 最后一个非叶子节点可能没有右子树
            if (2 * i +2 < length) {
                adjustMin(data,i);
            } else {
                // 没有右孩子
                if (data[2*i+1] < data[i]) {
                    swap(data, 2*i+1, i);
                }
            }
        }
        return data;
    }

    /**
     * 第一个节点和最后一个节点交换
     * 从上往下，从父节点、孩子节点中找到最小的和父节点交换
     * 直到被交换节点的前一个节点
     * @param data
     * @return
     */
    public int[] adjustMinHeap (int[] data) {

        int length = data.length;
        int index = length - 1;
        for (int i = index; i > 0; i++) {
            swap(data,0,i);
            int swap = data[i];
            int indexOf2 = (i-1)/2;
            for (int j = 0; j <= indexOf2; j++ ) {
                if (j == indexOf2) {
                    if (2*j+2 < length && data[2*j+2] == swap) {
                        if (data[2*j+1] < data[j]) {
                            swap(data,2*j+1,j);
                        }
                    }
                }else {
                    adjustMin(data,j);
                }
            }
        }
        return data;
    }

    public int[] adjustMin(int[] data,int j) {
         if (data[2*j+1] < data[2*j+2]) {
            if (data[2*j+1] < data[j]) {
                swap(data,2*j+1,j);
            }
        }else {
            if (data[2*j+2] < data[j]) {
                swap(data,2*j+2,j);
            }
        }
        return data;
    }
}
